package ljl.codetop300;

import java.util.Arrays;

/**
 * 这个是原版的最长递增子序列
 */
public class _300_l_i_s_0 {

  static class dp {
    public int lengthOfLIS(int[] nums) {
      if(nums.length == 0) return 0;
      int[] dp = new int[nums.length];
      int res = 0;
      Arrays.fill(dp, 1);
      for(int i = 0; i < nums.length; i++) {
        for(int j = 0; j < i; j++) {
          if(nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
        }
        res = Math.max(res, dp[i]);
      }
      return res;
    }
  }

  static class copydp {
    public int lengthOfLIS(int[] nums) {
      int[] dp = new int[nums.length];
      Arrays.fill(dp, 1);
      int res = 0;
      for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
          if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
        }
        res = Math.max(res, dp[i]);
      }
      return res;
    }
  }

  static class dp2 {
    /**
     * tails 含义变了，现在是长度为 i + 1 的子序列的最后一个元素是谁
     */
    public int lengthOfLIS(int[] nums) {
      int[] tails = new int[nums.length];
      int res = 0;
      for(int num : nums) {
        int i = 0, j = res;
        // 每次遍历时干两件事：当前这个数字，在已有的最长子序列里不是最大的
        // 那他只能进去代替掉第一个比他大的
        while(i < j) {
          int m = (i + j) / 2;
          if(tails[m] < num) i = m + 1;
          else j = m;
        }
        tails[i] = num;
        if(res == j) res++;
      }
      return res;
    }
  }

  static class copydp2 {
    public int lengthOfLIS(int[] nums) {
      int[] tails = new int[nums.length];
      int res = 0;
      for (int num : nums) {
        int l = 0, r = res;
        while (l < r) {
          int mid = (l + r) >>> 1;
          if (tails[mid] < num) l = mid + 1;
          else r = mid;
        }
        tails[l] = num;
        if (r == res) tails[res++] = num;
      }
      return res;
    }
  }
}
